package leetcodev1.链表;

public class LeetCode86 {

    public ListNode partition(ListNode head, int x) {
        ListNode smallHead = new ListNode(-1), smallIndex = smallHead;//小于x的链表组合
        ListNode bigHead = new ListNode(-1), bigIndex = bigHead;//大于等于x
        while (head != null) {
            int val = head.val;
            if (val >= x) {
                bigIndex.next = new ListNode(val);
                bigIndex = bigIndex.next;
            } else {
                smallIndex.next = new ListNode(val);
                smallIndex = smallIndex.next;
            }

            head = head.next;
        }

        smallIndex.next = bigHead.next;
        return smallHead.next;
    }
}

class Answer86 {
    //1.简洁
    //2.原地
    public ListNode partition(ListNode head, int x) {
        //这种重建的不需要重新赋值
        ListNode small = new ListNode(0);
        ListNode smallHead = small;
        ListNode large = new ListNode(0);
        ListNode largeHead = large;
        while (head != null) {
            if (head.val < x) {
                small.next = head;
                small = small.next;
            } else {
                large.next = head;
                large = large.next;
            }
            head = head.next;
        }
        large.next = null;//将最大的那个元素next置空即可
        small.next = largeHead.next;
        return smallHead.next;
    }
}
